//==============================================================================
//
//        DAvlTree - the avl tree collection class in the ofc-library
//
//               Copyright (C) 2003  Dick van Oudheusden
//  
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 3 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free
// Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
//==============================================================================
// 
//  $Date: 2008-07-19 12:28:58 $ $Revision: 1.9 $
//
//==============================================================================

#include "ofc/DAvlTree.h"


#if _INTERFACE_

#include "ofc/config.h"

#include "ofc/DComparable.h"

#include "ofc/DList.h"

typedef struct _DAvlNode
{
  id                   _key;
  id                   _object;
  struct _DAvlNode    *_left;
  struct _DAvlNode    *_right;
  struct _DAvlNode    *_parent;
  short                _balance;
  short                _trace;
} DAvlNode;


// The avl tree collection class implements a number of methods for creating, 
// inserting, searching and removing (elements in) an avl tree. The implementation is 
// inspired by the book "Algorithms & Data structures" by N. Wirth.
//
// @example
//
// #include <stdio.h>
// #include "ofc/DAvlTree.h"
// 
// int main(int argc, char *argv[])
// {
//   DAvlTree *tree = [DAvlTree alloc];
//   DText    *key  = [DText    new  ];
//   DText    *val;
// 
//   [tree init :[DText class]];            // Init tree, key is a DText object
// 
//   [key set :"Key1"];                     // Set key1 and create value1 for tree
//   val = [DText new]; [val set :"Value1"];
// 
//   [tree insert :key :val];
// 
//   [key set :"Key2"];                     // Set key1 and create value1 for tree
//   val = [DText new]; [val set :"Value2"];
// 
//   [tree insert :key :val];               // Create key2 and value2 for tree
// 
//   printf("Number of elements:%ld\n", [tree length]);  // Print tree length
// 
//   [key set :"Key2"];
//                                          // Check key present
//   printf("%s is %s present in tree\n", [key cstring], ([tree has :key] ? "" : "not"));
// 
//   val = [tree get :key];
//   printf("%s has value %s\n", [key cstring], (val != nil ? [val cstring] : "???"));
// 
//   [tree free];                           // Free tree and stored objects
//   [key  free];
// 
//   return 0;
// }
// 


@interface DAvlTree : DObject
{
@private
  DAvlNode     *_root;    // the root of the avl-tree
  Class         _class;   // the class of the key
  long          _count;   // the number of nodes in the avl tree
}

#endif


#define LEFT        -1
#define EQUAL        0
#define RIGHT        1

#if 0
  #define PLEFT(dest,node)  printf("%p->left:%p->%p\n ",dest,dest->_left,node);   dest->_left = node;
  #define PRIGHT(dest,node) printf("%p->right:%p->%p\n ",dest,dest->_right,node); dest->_right= node;
  #define PPARENT(dest,node) printf("%p->parent:%p->%p\n ",dest,dest->_parent,node); dest->_parent = node;
  #define PNEW(node)        printf("new %p ", node);
#else
  #define PLEFT(dest,node)   dest->_left = node;
  #define PRIGHT(dest,node)  dest->_right= node;
  #define PPARENT(dest,node) dest->_parent = node;
  #define PNEW(node)        
#endif




@implementation DAvlTree


#if _PRIVATE_

static DAvlNode *newNode(DAvlTree *tree, id key, id obj, DAvlNode *parent)
{
  DAvlNode *node = (DAvlNode *) objc_malloc(sizeof(DAvlNode));
  
  PNEW(node);
  
  node->_key     = [key copy];               // always store a copy of the key
  node->_object  = obj;
  node->_left    = NULL;
  node->_right   = NULL;
  node->_parent  = NULL;
  node->_balance = EQUAL;
  node->_trace   = EQUAL;

  PPARENT(node, parent);

  (tree->_count)++;
  
  return node;
}

static DAvlNode *copyNode(DAvlTree *tree, DAvlNode *orig, DAvlNode *parent)
{
  DAvlNode *node = (DAvlNode *) objc_malloc(sizeof(DAvlNode));
  
  PNEW(node);
  
  node->_key     = [orig->_key copy];           // always store a copy of the key
  node->_object  = orig->_object;               // store reference to node: shallow copy
  node->_left    = NULL;
  node->_right   = NULL;
  node->_parent  = NULL;
  node->_balance = orig->_balance;
  node->_trace   = orig->_trace;

  PPARENT(node, parent);

  (tree->_count)++;
  
  return node;
}

static void shallowFreeNode(DAvlNode *node)
{
  if (node->_key != nil) 
  {
    [node->_key free]; 
    
    node->_key = nil;
  }

  node->_object = nil;

  node->_left   = NULL;
  node->_right  = NULL;
  node->_parent = NULL;

  objc_free(node);
}

static void freeNode(DAvlNode *node)
{
  if (node->_object != nil)
    [node->_object free];

  shallowFreeNode(node);
}

static DAvlNode *getRoot(DAvlTree *tree)
{
  return tree->_root;
}

//
// Find the node with the smallest key in the given subtree
// 
// param node      the top of the subtree (<> nil)
//
// return the node with the smallest key
//

static DAvlNode *smallest(DAvlNode *node)
{
  while (node->_left != NULL)
  {
    node = node->_left;
  }

  return node;
}

//
// Find the node with the greatest key in the key subtree
//
// param node      the top of the subtree (<> NULL)
//
// return the node with the greatest key
//

static DAvlNode *greatest(DAvlNode *node)
{
  while (node->_right != NULL)
  {
    node = node->_right;
  }

  return node;
}


//
// Rotate the subtree on the left to restore the balance in the tree
//
// param top       the top of the subtree to be rotated
//
// return the new top
//

static DAvlNode *rotateLeft(DAvlNode *top)
{
  DAvlNode *old = top;

  top          = top->_right;
  PRIGHT(old,top->_left);
  if (top->_left != NULL)
  {
    PPARENT(top->_left,old);
  }
  PLEFT(top,old);
  PPARENT(top,old->_parent);
  PPARENT(old,top);

  if (top->_parent != NULL)
  {
    if (top->_parent->_trace == LEFT) 
    {
      PLEFT(top->_parent,top);
    }
    else
    {
      PRIGHT(top->_parent,top);
    }
  }
  
  return top;
}

//
// Rotate the subtree to the right to restore the balance in the tree
//
// param top       the top of the subtree to be rotated
//
// return the new top
//

static DAvlNode *rotateRight(DAvlNode *top)
{
  DAvlNode *old = top;

  top          = top->_left;
  PLEFT(old,top->_right);
  if (top->_right != NULL)
  {
    PPARENT(top->_right,old);
  }
  PRIGHT(top,old);
  PPARENT(top,old->_parent);
  PPARENT(old,top);

  if (top->_parent != NULL)
  {
    if (top->_parent->_trace == LEFT) 
    {
      PLEFT(top->_parent,top);
    }
    else
    {
      PRIGHT(top->_parent,top);
    }
  }
  
  return top;
}

//
// Determine consequence for a left grown tree
//
// param top       the top of the subtree 
//
// return continue balancing ?
//

static BOOL grownLeft(DAvlNode *top)
{
  switch(top->_balance)
  {
    case LEFT:
      {
        if (top->_left->_balance == LEFT) 
        {
          top->_balance = top->_left->_balance = EQUAL;
          top = rotateRight(top);
        } 
        else 
        {
          DAvlNode *tmp;
          
          switch (top->_left->_right->_balance) 
          {
            case LEFT:
              top->_balance = RIGHT;
              top->_left->_balance = EQUAL;
              break;

            case RIGHT:
              top->_balance = EQUAL;
              top->_left->_balance = LEFT;
              break;

            default:
              top->_balance = EQUAL;
              top->_left->_balance = EQUAL;
              break;
          }
          top->_left->_right->_balance = EQUAL;
          tmp = rotateLeft(top->_left); 
          top = rotateRight(top);
        }
      }
      return NO;

    case RIGHT:
      top->_balance = EQUAL;
      return NO;
  
    default:
      top->_balance = LEFT;
      return YES;
  }
}

//
// Determine consequence for a right grown tree
//
// param top       the top of the subtree 
//
// return continue balancing ?
//

static BOOL grownRight(DAvlNode *top)
{
  switch (top->_balance) 
  {
    case LEFT:          
      top->_balance = EQUAL;
      return NO;

    case RIGHT:
      {
        DAvlNode *tmp;

        if (top->_right->_balance == RIGHT) 
        { 
          top->_balance = top->_right->_balance = EQUAL;

          top = rotateLeft(top);
        }
        else 
        {
          switch (top->_right->_left->_balance) 
          {
            case RIGHT:
              top->_balance = LEFT;
              top->_right->_balance = EQUAL;
              break;

            case LEFT:
              top->_balance = EQUAL;
              top->_right->_balance = RIGHT;
              break;

            default:
              top->_balance = top->_right->_balance = EQUAL;
              break;
          }
          top->_right->_left->_balance = EQUAL;
          tmp = rotateRight(top->_right); 
          top = rotateLeft(top);
        }
      }
      return NO;

    default:
      top->_balance = RIGHT;
      return YES;
  }
}

//
// Determine consequence for a left shrunk tree
//
// param top       the top of the subtree 
//
// return the new top of the subtree (or NULL if balanced)
//

static DAvlNode *shrunkLeft(DAvlNode *top)
{
  switch (top->_balance) 
  {
    case LEFT:
      top->_balance = EQUAL;
      return top;

    case RIGHT:
      if (top->_right->_balance == RIGHT) 
      {
        top->_balance = top->_right->_balance = EQUAL;
        top = rotateLeft(top);
        return top;
      }
      else if (top->_right->_balance == EQUAL) 
      {
        top->_balance = RIGHT;
        top->_right->_balance = LEFT;
        top = rotateLeft(top);
        return NULL;
      }
      else 
      {
        DAvlNode *tmp;
        
        switch (top->_right->_left->_balance) 
        {
          case LEFT:
            top->_balance = EQUAL;
            top->_right->_balance = RIGHT;
            break;

          case RIGHT:
            top->_balance = LEFT;
            top->_right->_balance = EQUAL;
            break;

          default:
            top->_balance = EQUAL;
            top->_right->_balance = EQUAL;
            break;
        }
        top->_right->_left->_balance = EQUAL;
        top->_trace = RIGHT;
        tmp = rotateRight(top->_right);
        top = rotateLeft(top);
        return top;
      }

    default:
      top->_balance = RIGHT;
      return NULL;
  }
}

//
// Determine consequence for a right shrunk tree
//
// param top       the top of the subtree 
//
// return the new top of the subtree (or NULL if balanced)
//

static DAvlNode *shrunkRight(DAvlNode *top)
{
  switch (top->_balance) 
  {
    case RIGHT:
      top->_balance = EQUAL;
      return top;

    case LEFT:
      if (top->_left->_balance == LEFT) 
      {
        top->_balance = top->_left->_balance = EQUAL;
        top = rotateRight(top);
        return top;
      }
      else if (top->_left->_balance == EQUAL) 
      {
        top->_balance = LEFT;
        top->_left->_balance = RIGHT;
        top = rotateRight(top);
        return NULL;
      }
      else 
      {
        DAvlNode *tmp;
        
        switch (top->_left->_right->_balance) 
        {
          case LEFT:
            top->_balance = RIGHT;
            top->_left->_balance = EQUAL;
            break;

          case RIGHT:
            top->_balance = EQUAL;
            top->_left->_balance = LEFT;  
            break;
      
          default:
            top->_balance = EQUAL;
            top->_left->_balance = EQUAL;
        }
        top->_left->_right->_balance = EQUAL;
        top->_trace = LEFT;
        tmp = rotateLeft(top->_left);
        top = rotateRight(top);
        return top;
      }

    default:
      top->_balance = LEFT;
      return NULL;
  }
}
#endif

//// Constructors

//
// Initialise to an unitialised avl tree (not implemented)
//
// @return the object
//

- (DAvlTree *) init
{
  [super init];
  
  WARNING(DW_METHOD_NOT_IMPL, "init");

  return self;
}

//
// Initialise to an empty avl tree
//
// @param key       the class of the key
//
// @return the object
//

- (DAvlTree *) init :(Class) key
{
  [super init];

  if (key == nil)
  {
    WARNING(DW_INVALID_ARG, "key");
  }
  else if (![key isClass])
  {
    WARNING(DW_ARG_NOT_CLASS, "key");
  }
  else if (![key conformsTo :@protocol(DComparable)])
  {
    WARNING(DW_PROT_NOT_IMPL, "DComparable");
  }

  _class     = key;
  _root      = NULL;
  _count     = 0;

  return self;
}


//// Copy related methods

//
// Do a shallow copy of the avl tree
// 
// @return the object
// 
- shallowCopy
{
  DAvlTree *copy = [super shallowCopy];
  
  DAvlNode *nWalk   = NULL; // copied tree
  DAvlNode *nParent = NULL;
  
  DAvlNode *oWalk   = _root; // original tree

  copy->_count  = 0;
  
  if (oWalk != NULL)
  {
    nWalk = copyNode(copy, oWalk, nParent);
    
    copy->_root = nWalk;
  }
  
  while (oWalk != NULL)
  {
    if (oWalk->_left != NULL)
    {
      oWalk = oWalk->_left;
      
      nParent = nWalk;
      
      nWalk = copyNode(copy, oWalk, nParent);
      
      nParent->_left = nWalk;
    }
    else if (oWalk->_right != NULL)
    {
      oWalk = oWalk->_right;
      
      nParent = nWalk;
      
      nWalk = copyNode(copy, oWalk, nParent);
      
      nParent->_right = nWalk;
    }
    else
    {
      DAvlNode *last = oWalk;
      
      oWalk = oWalk->_parent;
      nWalk = nWalk->_parent;
      
      while ((oWalk != NULL) && ((oWalk->_right == NULL) || (oWalk->_right == last)))
      {
        last = oWalk;
        
        oWalk = oWalk->_parent;
        nWalk = nWalk->_parent;
      }
      
      if (oWalk != NULL)
      {
        oWalk = oWalk->_right;
        
        nParent = nWalk;
        
        nWalk = copyNode(copy, oWalk, nParent);

        nParent->_right = nWalk;
      }
    }
  }
  
  return copy;
}

//
// Deepen a copied avl tree
//
// @return the object
//
- deepen
{
  DAvlNode *walk    = _root;
  
  [super deepen];

  if (walk != NULL)
  {
    walk->_object = [walk->_object copy];
  }
  
  while (walk != NULL)
  {
    if (walk->_left != NULL)
    {
      walk = walk->_left;

      walk->_object = [walk->_object copy];
    }
    else if (walk->_right != NULL)
    {
      walk = walk->_right;
      
      walk->_object = [walk->_object copy];
    }
    else
    {
      DAvlNode *last = walk;
      
      walk = walk->_parent;
      
      while ((walk != NULL) && ((walk->_right == NULL) || (walk->_right == last)))
      {
        last = walk;
        
        walk = walk->_parent;
      }
      
      if (walk != NULL)
      {
        walk = walk->_right;
        
        walk->_object = [walk->_object copy];
      }
    }
  }
  
  return self;
}


//// Deconstructors

//
// Free the avl tree (keys are freed, objects are *NOT* freed)
//
// @return the object
//

- shallowFree
{
  DAvlNode *node;
  DAvlNode *next;

  node = _root;
  while (node != NULL)
  {
    if (node->_left != NULL)
    {
      next = node->_left;
      
      node->_left = NULL;
    }
    else if (node->_right != NULL)
    {
      next = node->_right;

      node->_right = NULL;
    }
    else
    {
      next = node->_parent;

      shallowFreeNode(node);

      _count--;
    }
    node = next;
  }

  [super free];

  return self;
}

//
// (Deep) free the avl tree (keys are freed, objects are *FREED*)
//
// @return the object
//

- free
{
  DAvlNode *node;
  DAvlNode *next;

  node = _root;
  while (node != NULL)
  {
    if (node->_left != NULL)
    {
      next = node->_left;
      
      node->_left = NULL;
    }
    else if (node->_right != NULL)
    {
      next = node->_right;

      node->_right = NULL;
    }
    else
    {
      next = node->_parent;

      freeNode(node);

      _count--;
    }
    node = next;
  }

  [super free];

  return self;
}


//// Member methods

//
// Return the number of objects in the tree
//
// @return the length
//

- (long) length
{
  return _count;
}

//
// Check if the avl tree is empty
//
// @return is it?
//

- (BOOL) isEmpty
{
  return (_count == 0);
}


//// Avl tree manipulation

//
// Insert a key,object in the avl tree
//
// @param key      the key to be inserted
// @param object   the object to be inserted
//
// @return success
//

- (BOOL) insert :(id) key :(id) object
{
  if (key == nil)
  {
    WARNING(DW_INVALID_ARG, "key");

    return NO;
  }
  else if (![key isKindOf :_class])
  {
    WARNING(DW_INVALID_CLASS, "key");

    return NO;
  }

  if (_root == NULL)
  {
    _root = newNode(self, key, object, NULL);
  }
  else
  {
    DAvlNode *node    = _root;
    BOOL      balance = YES;
    BOOL      found   = NO;

    // search the location to insert

    while (!found)
    {
      int cmp = [key compare :node->_key];

      if (cmp == 0)
      {
        node->_object = object;
        
        balance = NO;
        found   = YES;
      }
      else if (cmp < 0)
      {
        node->_trace = LEFT;

        if (node->_left == NULL)
        {
          DAvlNode *next = newNode(self, key, object, node);
          PLEFT(node, next); //node->_left = [self addNode :key :object :node];
          
          found = YES;
        }
        else
        {
          node = node->_left;
        }
      }
      else
      {
        node->_trace = RIGHT;

        if (node->_right == NULL)
        {
          DAvlNode *next = newNode(self, key, object, node);
          PRIGHT(node, next ); //node->_right = [self addNode :key :object :node];

          found = YES;
        }
        else
        {
          node = node->_right;
        }
      }
    }

  // node added to list, rebalance
    while ((balance) && (node != NULL))
    {
      if (node->_trace == LEFT)
      {
        balance = grownLeft(node);
      }
      else if (node->_trace == RIGHT)
      {
        balance = grownRight(node);
      }
      else
        balance = NO;

      node = node->_parent;
    }

    // root can be moved, fix this
    while (_root->_parent != NULL)
    {
      _root = _root->_parent;
    }
  }
  return YES;
}

//
// Remove a key,object from the avl tree
//
// @param key      the key to be removed
//
// @return the object that is removed (or nil for not found)
//

- (id) delete :(id) key
{
  DAvlNode *node    = _root;
  BOOL      found   = NO;
  DAvlNode *target  = NULL;
  id        object  = nil;
  
  if (key == nil)
  {
    WARNING(DW_INVALID_ARG, "key");

    return nil;
  }
  else if (![key isKindOf :_class])
  {
    WARNING(DW_INVALID_CLASS, "key");

    return nil;
  }

                                                     // search the key to delete
  while ((node != NULL) && (!found))
  {
    int cmp = [key compare :node->_key];

    if (cmp == 0)
    {
      DAvlNode *parent = NULL;

      object = node->_object;

      if (node->_left != NULL)
      {
        target = node;
        
        node->_trace = LEFT;
        node = node->_left;

        while (node->_right != NULL)
        {
          node->_trace = RIGHT;
          node = node->_right;
        }

        target->_key    = node->_key;    node->_key = nil;
        target->_object = node->_object; node->_object = nil;

        parent = node->_parent;
        if (parent->_trace == LEFT)
        {
          PLEFT(parent,node->_left); 
        }
        else
        {
          PRIGHT(parent,node->_left); 
        }
        if (node->_left != NULL)
        {
          PPARENT(node->_left,parent); 
        }
      }
      else if (node->_right != NULL)
      {
        target = node;

        node->_trace = RIGHT;
        node = node->_right;

        while (node->_left != NULL)
        {
          node->_trace = LEFT;
          node = node->_left;
        }

        target->_key    = node->_key;      node->_key    = nil;
        target->_object = target->_object; node->_object = nil;
          
        parent = node->_parent;
        if (parent->_trace == LEFT)
        {
          PLEFT(parent,node->_right); 
        }
        else
        {
          PRIGHT(parent,node->_right); 
        }
        if (node->_right != NULL)
        {
          PPARENT(node->_right,parent); 
        }
      }
      else
      {
        parent = node->_parent;
        
        if (parent != NULL)
        {          
          if (parent->_trace == RIGHT)
          {
            PRIGHT(parent,NULL); 
          }
          else
          {
            PLEFT(parent,NULL); 
          }
        }
        else
          _root = NULL;
      }

      shallowFreeNode(node); 
      _count--; 
      node = parent;
      found = YES;
    }
    else if (cmp < 0)
    {
      node->_trace = LEFT;
      node = node->_left;
    }
    else
    {
      node->_trace = RIGHT;
      node = node->_right;
    }
  }

                                            // node removed to list, rebalance
  while (node != NULL)
  {
    if (node->_trace == LEFT)
    {
      node = shrunkLeft(node);
    }
    else if (node->_trace == RIGHT)
    {
      node = shrunkRight(node);
    }
    else
      node = NULL;

    node = (node != NULL) ? node->_parent : NULL;
  }

  // root can be moved, fix this
  while ((_root != NULL) && (_root->_parent != NULL))
  {
    _root = _root->_parent;
  }

  return object;
}

//
// Check if the avl tree contains a key
//
// @param key      the key to be checked
//
// @return is the key present
//

- (BOOL) has :(id) key
{
  DAvlNode *node  = NULL;
  DAvlNode *found = NULL;

  if (key == nil)
  {
    return NO;
  }

  if (![key isKindOf :_class])
  {
    WARNING(DW_INVALID_CLASS, "key");

    return NO;
  }

  node  = _root;

  while ((node != NULL) && (found == NULL))
  {
    int cmp = [key compare :node->_key];

    if (cmp == 0)
    {
      found = node;
    }
    else if (cmp < 0)
    {
      node = node->_left;
    }
    else
    {
      node = node->_right;
    }
  }

  return (found != NULL);
}

//
// Return the object related to a key
//
// @param key      the key 
//
// @return the object related to the key (or nil)
//

- get :(id) key
{
  DAvlNode *node  = NULL;
  DAvlNode *found = NULL;


  if (key == nil)
  {
    return nil;
  }

  if (![key isKindOf :_class])
  {
    WARNING(DW_INVALID_CLASS, "key");

    return nil;
  }


  node  = _root;

  while ((node != NULL) && (found == NULL))
  {
    int cmp = [key compare :node->_key];

    if (cmp == 0)
    {
      found = node;
    }
    else if (cmp < 0)
    {
      node = node->_left;
    }
    else
    {
      node = node->_right;
    }
  }

  return (found != NULL) ? found->_object : nil;
}


//// List related functions

//
// Return a list with copies of all keys (sorted) in the avl tree
//
// @return a (new) sorted list with all the keys
//

- (DList *) keys
{
  DList        *list = [DList alloc];
  DAvlIterator *iter = [DAvlIterator alloc];
  id            key  = nil;

  [list init];
  
  [iter init :self];  
  [iter first];
  
  key = [iter key];
  while (key != nil)
  {
    [list append :[key copy]];

    [iter next];
    key = [iter key];
  }
  [iter free];
  
  return list;
}

//
// Return a list with copies of all keys (reverse sorted) in the avl tree
//
// @return a (new) reverse sorted list with all the keys
//

- (DList *) rkeys
{
  DList        *list = [DList alloc];
  DAvlIterator *iter = [DAvlIterator alloc];
  id            key  = nil;

  [list init];
  
  [iter init :self];  
  [iter last];
  
  key = [iter key];
  while (key != nil)
  {
    [list append :[key copy]];

    [iter prev];
    key = [iter key];
  }
  [iter free];
  
  return list;
}

//
// Return a list with copies of all the objects in the avl tree
//
// @return a (new) list with all the objects
//

- (DList *) objects
{
  DList        *list = [DList alloc];
  DAvlIterator *iter = [DAvlIterator alloc];
  id            obj  = nil;

  [list init];
  [iter init :self];
  
  obj = [iter first];
  
  while (obj != nil)
  {
    [list append :[obj copy]];

    obj = [iter next];
  }
  [iter free];

  return list;
}

#if 0
static void show(DAvlNode *node)
{
  if (node  != NULL)
  {
    printf("%p->(", node);

    if (node->_left != NULL)
    {
      printf("%p,", node->_left);
    }
    else
      printf("?,");


    if (node->_right != NULL)
    {
      printf("%p)", node->_right);
    }
    else
      printf("?)");
    printf(" ");

    show(node->_left);
    show(node->_right);
  }
}

static void check(DAvlNode *node, int *cnt)
{
  if (node  != NULL)
  {
    if (node->_left != NULL)
    {
      if (node->_left->_parent != node)
      {
        (*cnt)++;
        printf("Parent check failed for %p!\n",node->_left);
      }
      check(node->_left,cnt);
    }
    if (node->_right != NULL)
    {
      if (node->_right->_parent != node)
      {
        (*cnt)++;
        printf("Parent check failed for %p!\n", node->_right);
      }
      check(node->_right,cnt);
    }
  }
}

static void count(DAvlNode *node, int *cnt)
{
  if (node  != NULL)
  {
    (*cnt)++;

    count(node->_left, cnt);
    count(node->_right, cnt);
  }
}

//
// Show the tree
//

- (void) show
{
  show(_root);
}

//
// Count the nodes
//
// @return the number of nodes
//

- (int) count
{
  int cnt = 0;
  
  count(_root, &cnt);

  return cnt;
}

//
// Check the parent pointers
//
// @return the number of wrong parent pointers
//

- (int) check
{
  int cnt = 0;
  
  check(_root, &cnt);

  return cnt;
}
#endif

@end


#if _INTERFACE_

//
// The DAvlIterator class contains a number of methods for iterating a avl tree.
//
// @example
// #include <stdio.h>
// #include "ofc/DAvlTree.h"
//
// int main(int argc, char *argv[])
// {
//   DAvlTree     *tree = [DAvlTree     alloc];
//   DAvlIterator *iter = [DAvlIterator alloc];
//
//   DText        *key;
//   DText        *value;
//
//   [tree init :[DText class]];            // Init tree, key is a DText object
//
//   // Insert DText keys and values in the tree ...
//
//   [iter init :tree];                     // Init the iterator with the tree
//
//   key = [iter key];
//   while (key != nil)                     // Iterate the tree
//   {
//     val = [iter object];
//
//     [iter next];
//     key = [iter key];
//   }
//
//   [iter free];                           // Cleanup
//   [tree free];
//   [key  free];
//
//   return 0;
// }
//

@interface DAvlIterator : DObject
{
@private
  DAvlTree       *_tree;    // the tree on which the iterator operates
  DAvlNode       *_node;    // the current node in the list
}

#endif



@implementation DAvlIterator

//// the constructors

//
// Initialises an avl tree iterator without a tree
//
// @return the iterator
//

- (DAvlIterator *) init
{
  [super init];
  
  _tree    = nil;
  _node   = NULL;
  
  return self;
}

//
// Initialises an iterator on a tree (the iterator is moved to the first node)
//
// @param tree    the tree on which the iterator operates
//
// @return the iterator
//

- (DAvlIterator *) init :(DAvlTree *) tree
{
  [self init];

  [self tree :tree];

  return self;
}



//// the iterator methods

//
// Set the avl tree (iterator is moved to the first object)
//
// @return the object
//

- (DAvlIterator *) tree :(DAvlTree *) tree
{
  _tree = tree;

  [self first];
  
  return self;
}

//
// Get the first object in the tree
//
// @return a reference to the first object (or nil)
//

- (id) first
{
  _node = NULL;

  if (_tree != nil)
  {
    _node = getRoot(_tree);

    if (_node != NULL)
    {
      _node = smallest(_node);
    }
  }
  
  return (_node != NULL) ? _node->_object : nil;
}

//
// Get the next object in the tree
//
// @return the next object (or nil)
//

- (id) next
{
  if (_node != NULL)
  {
    if (_node->_right != NULL)
    {
      _node = smallest(_node->_right);
    }
    else
    {
      while ((_node->_parent != NULL) && (_node->_parent->_right == _node))
      {
        _node = _node->_parent;
      }

      if (_node->_parent != NULL)
      {
        if (_node->_parent->_left == _node)
        {
          _node = _node->_parent;
        }
      }
      else
        _node = NULL;
    }
  }

  return (_node != NULL) ? _node->_object : nil;
}

//
// Get the previous object in the tree
//
// @return the previous object (or nil)
//

- (id) prev
{
  if (_node != NULL)
  {
    if (_node->_left != NULL)
    {
      _node = greatest(_node->_left);
    }
    else
    {
      while ((_node->_parent != NULL) && (_node->_parent->_left == _node))
      {
        _node = _node->_parent;
      }

      if (_node->_parent != NULL)
      {
        if (_node->_parent->_right == _node)
        {
          _node = _node->_parent;
        }
      }
      else
        _node = NULL;
    }
  }

  return (_node != NULL) ? _node->_object : nil;
}

//
// Get the last object in the tree
//
// @return the last object (or nil)
//

- (id) last
{
  _node = NULL;

  if (_tree != nil)
  {
    _node = getRoot(_tree);

    if (_node  != NULL)
    {
      _node = greatest(_node);
    }
  }
  
  return (_node != NULL) ? _node->_object : nil;
}

//
// Set the current object to another object
//
// @param object   the object to be placed in current node
//
// @return the previous stored object
//

- (id) object :(id) object
{
  id old = nil;
  
  if (_node != NULL)
  {
    old = _node->_object;
    
    _node->_object = object;
  }
  
  return old;
}

//
// Get the current object
//
// @return the current object (or nil)
//

- (id) object
{
  return (_node != NULL) ? _node->_object : nil;
}

//
// Get the key of the current object
//
// @return a referencee to the key of the current object (or nil)
//

- (id) key
{
  return (_node != NULL) ? _node->_key : nil;
}

@end

/*==========================================================================*/
